# -*- coding:utf-8 -*-
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None
class Solution:
    def GetNext(self, pNode):
        # write code here
        if pNode.right:#有右子树
            p=pNode.right
            while p.left:
                p=p.left
            return p
        while pNode.next:#无右子树，则找第一个当前节点是父节点左孩子的节点
            if(pNode.next.left==pNode):
                return pNode.next
            pNode = pNode.next#沿着父节点向上遍历，中序是从左开始
        return  #到了根节点仍没找到，则返回空
'''
1. 有右孩子，取右孩子的左孩子节点，左根右
右孩子的根节点不是下一个，下一个是右孩子的左孩子
2. 当前节点是父节点的左孩子
找的是中序遍历顺序的下一个节点，也就是当前节点的父节点的父节点
'''
class Solution:
    def GetNext(self, pNode):
        # write code here
        if not pNode:
            return None
        if pNode.right:
            p = pNode.right
            while p.left:
                p = p.left
            return p
        p = pNode
        while True:
            if p.next and p.next.left == p:
                return p.next
            if not p.next:
                return None
            p = p.next